package tree.test337;

import listbyorder.utils.TreeNode;

import java.util.HashMap;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/18 8:30
 */
public class Solution1 {

    HashMap<TreeNode, Integer> mapN = new HashMap<>();
    HashMap<TreeNode, Integer> mapY = new HashMap<>();

    public int rob(TreeNode root) {
        if (root == null) return 0;
        // 不考虑当前的头节点
        int dn = dfsn(root);
        // 考虑当前的头节点
        int dy = dfsy(root);
        return Math.max(dn, dy);
    }

    private int dfsn(TreeNode root) {
        if (root == null) return 0;
        if (mapN.containsKey(root)) {
            return mapN.get(root);
        }
        int res = Math.max(Math.max(dfsy(root.left) + dfsy(root.right), dfsn(root.left) + dfsn(root.right)),
                    Math.max(dfsy(root.left) + dfsn(root.right), dfsn(root.left) + dfsy(root.right)));
        mapN.put(root, res);
        return res;
    }

    private int dfsy(TreeNode root) {
        if (root == null) return 0;
        if (mapY.containsKey(root)) return mapY.get(root);
        int res = root.val + dfsn(root.left) + dfsn(root.right);
        mapY.put(root, res);
        return res;
    }
}
